/**
 * Copyright (c) 2012, David Varbel
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
 * 
 * 1) Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
 * 2) Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.epistrata.neutraltheory;

import java.lang.ref.WeakReference;
import java.util.LinkedList;

/**
 * @author dvarbel
 *
 */
public class Grid {
	private GridCell[][] gridCells;
	private double[] cellSize = new double[2];
	private int[] gridSize = new int[2];
	
	public static class GridCell {
		
		private LinkedList<Critter> critters = new LinkedList<Critter>();
		private int column;
		private int row;

		public GridCell(int column, int row) {
			if (column < 0 || row < 0) {
				throw new IllegalArgumentException("Neither the column nor row may be less than zero.");
			}
			this.column = column;
			this.row = row;
		}
		
		public void clearCritters() {
			critters.clear();
		}
		
		public void addCritter(Critter critter) {
			critters.add(critter);
		}
		
		public LinkedList<Critter> getCritters() {
			return critters;
		}
		
		public int getPopulationCount() {
			return critters.size();
		}
		
		public int getColumn() {
			return column;
		}

		public int getRow() {
			return row;
		}
		
		public void removeCritter(Critter critter) {
			if (critter == null) {
				throw new IllegalArgumentException("A non-null critter must be provided.");
			}
			
			boolean removed = critters.remove(critter);
			if (!removed) {
				throw new IllegalArgumentException("Critter could not be removed from grid cell because critter was not in grid cell.");
			}
		}
	}
	

	public Grid(NeutralTheoryModel model) {
		if (model == null) {
			throw new IllegalArgumentException("A non-null Model must be provided.");
		}

		/*
		 * determine size for cell grid, each cell must be larger than the maximum spacial distance
		 * for mating, and there should be a whole number of cells in each direction
		 */
		int xSize = (int) Math.floor(model.getWorldXSize() / (model.getSpacialDistance() * 1.01d));
		int ySize = (int) Math.floor(model.getWorldYSize() / (model.getSpacialDistance() * 1.01d));
		double cellX = model.getWorldXSize() / xSize;
		double cellY = model.getWorldYSize() / ySize;
		
		//if the values don't make sense, just set them to one rather than fail
		if (xSize <= 0) {
			xSize = 1;
		}
		if (ySize <= 0) {
			ySize = 1;
		}
		if (cellX <= 0) {
			cellX = 1;
		}
		if (cellY <= 0) {
			cellY = 1;
		}
		
		gridCells = new GridCell[xSize][ySize];
		for (int i = 0; i < xSize; i++) {
			for (int j = 0; j < ySize; j++) {
				gridCells[i][j] = new GridCell(i, j);
			}
		}
		gridSize[0] = xSize;
		gridSize[1] = ySize;
		cellSize[0] = cellX;
		cellSize[1] = cellY;
	}
	
	public void clear() {
		for (int i = 0; i < gridSize[0]; i++) {
			for (int j = 0; j < gridSize[1]; j++) {
				gridCells[i][j].clearCritters();
			}
		}
	}

	/**
	 * 
	 * @param previousGridCell GridCell before change in location
	 * @param critter Critter with location already updated
	 * @return new GridCell after change in location
	 */
	public GridCell updateCritterLocation(Critter critter) {
		if (critter == null) {
			throw new IllegalArgumentException("A non-null critter must be provided.");
		}
		double[] loc = critter.getLocation();
		int gridColumn = xLocToGridCol(loc[0]);
		int gridRow = yLocToGridRow(loc[1]);

		GridCell previousGridCell = critter.getCurrentGridCell();
		if (previousGridCell == null) {
			gridCells[gridColumn][gridRow].addCritter(critter);
			return gridCells[gridColumn][gridRow];
		}
		//check if cell changed
		if (previousGridCell.getColumn() != gridColumn || previousGridCell.getRow() != gridRow) {
			previousGridCell.removeCritter(critter);
			gridCells[gridColumn][gridRow].addCritter(critter);
			return gridCells[gridColumn][gridRow];
		} else {
			return previousGridCell;
		}
		
	}

	public GridCell getCellAt(int column, int row) {
		if (column < 0 || column >= gridSize[0]) {
			throw new IllegalArgumentException("Invalid column specified.");
		}
		if (row < 0 || row >= gridSize[1]) {
			throw new IllegalArgumentException("Invalid row specified.");
		}

		return gridCells[column][row]; 
	}

	/**
	 * Returns the critters in all grid cells within radius of the current grid cell of centerCritter.  Note that the returned list will include the center critter provided in the arugment.
	 * 
	 * @param centerCritter
	 * @param radius size of neighborhood
	 * @return an array of all the critters, or an empty array if there are none
	 */
	public LinkedList<Critter> getCrittersInNeighborhood(Critter centerCritter, double radius) {
		if (centerCritter.getCurrentGridCell() != getCellAt(xLocToGridCol(centerCritter.getLocation()[0]), yLocToGridRow(centerCritter.getLocation()[1]))) {
			throw new IllegalArgumentException("Center critter current cell is not the correct current cell for the critter's location.");
		}
		if (radius <= 0.0) {
			throw new IllegalArgumentException("Radius must be > 0.");
		}
		
		//convert radius to cell distance
		int cellDistance = (int) Math.ceil(radius/Math.min(cellSize[0], cellSize[1]));  //TODO works even if not the same size in both dimensions, but will become inefficient if they are dramatically different
		
		LinkedList<Critter> neighborCritters = new LinkedList<Critter>();
		
		int centerColumn = centerCritter.getCurrentGridCell().getColumn();
		int centerRow = centerCritter.getCurrentGridCell().getRow();
		for (int columnCounter = 0; columnCounter < (cellDistance * 2); columnCounter++) {
			int column = centerColumn - cellDistance + columnCounter;
			//make sure we are still in the grid.  wrap around in either direction.  taurus topology.
			if (column < 0 || column >= gridSize[0]) {
				column = column < 0 ? column + gridSize[0] : column - gridSize[0];
			}
			for (int rowCounter = 0; rowCounter < (cellDistance * 2); rowCounter++) {
				int row = centerRow - cellDistance + rowCounter;
				//make sure we are still in the grid.  wrap around in either direction.  taurus topology.
				if (row < 0 || row >= gridSize[1]) {
					row = row < 0 ? row + gridSize[1] : row - gridSize[1];
				}
				neighborCritters.addAll(gridCells[column][row].getCritters());
			}
		}
		
		return neighborCritters;
	}
	
	/**
	 * @return the cellSize
	 */
	public double[] getCellSize() {
		return cellSize;
	}

	/**
	 * @return the gridSize
	 */
	public int[] getGridSize() {
		return gridSize;
	}

	/**
	 * @return the gridSize
	 */
	public int getTotalCritterCount() {
		int size = 0;
		for (int i = 0; i < gridSize[0]; i++) {
			for (int j = 0; j < gridSize[1]; j++) {
				size += gridCells[i][j].getPopulationCount();
			}
		}
		return size;
	}

	private int xLocToGridCol(double x) {
		return (int) Math.floor(x / cellSize[0]);
	}

	private int yLocToGridRow(double y) {
		return (int) Math.floor(y / cellSize[1]);
	}

}
